1. Field of the Invention
The invention relates to real-time embedded processors, and in particular, to a method and system for handling interrupts and traps in a multi-threaded processor without introducing priority inversion and unwanted re-entrancy.
2. Discussion of Related Art
An embedded system is a system that includes an embedded processor for controlling the behavior of that system. For example, modern automobiles, home appliances, personal electronics, and entertainment systems all typically include at least one embedded processor. These embedded systems are increasingly being required to provide “real-time” operation—i.e., the system must provide accurate and timely responses to external events. One of the keys to real-time performance is that a system respond to interrupt requests within a very short time period (e.g., tens of clock cycles). Therefore, real-time embedded processors typically should not queue interrupt requests and then service them on a scheduled basis.
As real-time embedded systems become ever more complex, the use of multithreaded code in such systems becomes increasingly appealing. Multithreaded code allows a processor to hold the state of several active threads. Each of the active threads can be executed independently, so that when one of the threads becomes blocked (e.g., due to a cache miss) another thread can be executed so that processor cycles are not wasted. This thread switching capability can significantly enhance system responsiveness by making more efficient use of processor capacity. In addition, multithreading allows state information to be efficiently shared among the active threads, and can therefore reduce the size and cost of the resources required for a given system.
Unfortunately, the conventions of real-time embedded systems can conflict with the desired operating characteristics of multithreaded code. For example, as noted above, real-time systems respond to all interrupt requests almost immediately. However, in a multi-threaded system (i.e., a system running multi-threaded code), accepting interrupt requests as soon as such requests are made can result in “priority inversion.” In a multi-threaded system, the active threads are assigned thread priority values that determine which active thread is actually executed at a particular point in time. Priority inversion occurs when a lower-priority thread prevents a higher-priority thread from executing, which can result in a critical deadline being missed, which in turn can lead to system failure.
FIG. 1 shows an operational diagram for a multi-threaded system that includes two active threads T0 and T1. As indicated by the “THREAD PRIORITY” axis, thread T0 is assigned a higher priority than thread T1. At a time t0, thread T0 is executing (indicated by the diagonal hatching), while thread T1 is held pending (indicated by the solid white fill). At a time t1, a blocking event (such as a cache miss) occurs, and the execution of thread T0 is halted (indicated by the cross-hatching). Because thread T0 is blocked, lower-priority thread T1 then begins executing at time t1.
At a time t2, an interrupt request is generated, at which point an interrupt handler IH1 associated with thread T1 begins servicing the requested (low-priority) interrupt INT1. Because interrupt handler IH1 is still servicing interrupt INT1 when thread T0 becomes unblocked at a time t3, thread T0 cannot resume execution until the interrupt handler is finished with interrupt INT1 at a time t4. Thus, for the period from time t3 to time t4, threads T0 and T1 are in priority inversion, with the execution of high-priority thread T0 being pre-empted by the low-priority interrupt INT1, and therefore low-priority thread T1.
Traps (i.e., internally generated responses to internal conditions, such as error conditions) pose a similar problem for multi-threaded systems. Trap routines rely on the traceable nature of a trap to resolve and rectify a problem, and then restart the task that caused the trap. However, multi-threaded systems can encounter difficulties with trap handling due to the fact that traps can be either synchronous or asynchronous. A synchronous trap occurs during or immediately after the instruction that led to the trap condition, whereas an asynchronous trap can occur some time after the causal instruction. Therefore, in a multi-threaded system, by the time an asynchronous trap is generated, a thread switch or multiple thread switches may have already occurred. This can make the thread that originated the trap difficult to identify, which in turn can lead to problems servicing the trap.
Furthermore, because the multiple active threads of a multi-threaded system can all generate trap conditions, a trap condition from one thread can be generated while a trap from another thread is being serviced. For example, FIG. 2 shows an operational diagram for a multi-threaded system that includes two active threads T0 and T1. As in FIG. 1, thread T0 is assigned a higher priority than thread T1, as indicated by the “THREAD PRIORITY” axis. At a time t0, thread T0 is executing (indicated by the diagonal hatching), while thread T1 is held pending (indicated by the solid white fill). At a time t1, a blocking event for thread T0 occurs, and the execution of thread T0 is disabled (indicated by the cross-hatching). Because thread T0 is blocked, lower-priority thread T1 begins executing at time t1.
At a time t2, thread T1 generates a low priority trap TR1. Because thread T1 is executing at the time trap TR1 is generated, trap TR1 is a synchronous trap. Thread T1 branches to a trap handler TH1 and begins servicing trap TR1 at time t2. However, before this servicing of trap TR1 is completed, thread T0 generates a higher-priority asynchronous trap TR0 at time t3. Because trap TR0 has a higher priority than trap TR1, thread T0 branches to a trap handler TH0 and immediately begins servicing trap TR0 even though trap TR1 has not been fully serviced. Because both trap handlers TH0 and TH1 may use the same shared resources, trap TR0 is unintentionally re-entrant (indicated by the solid black fill). Therefore, trap TR0 may be serviced incorrectly due to ill-defined information states resulting from the incomplete operation of trap handler TH1. Interrupted trap handler TH1 may also fail to execute properly due to this unexpected re-entrancy.
Thus, it is desirable to provide a method and system for allowing a real-time embedded system to run multi-threaded code that properly handles interrupts without generating priority inversion conditions, and properly handles traps without causing unintended trap re-entrancy.